\section{Uncertainty Track}

The uncertainty part of the IPC was initiated in 2004 by Michael
Littman and H{\aa}kan Younes with the introduction of PPDDL, the
probabilistic extension of PDDL~\cite{ippc04}.  PPDDL extends PDDL
with stochastic action effects, allowing a variety of Markov Decision
Processes (MDPs) to be encoded in a relational PDDL-like manner.  The
2006 competition (Givan \& Bonet) added a track for Conformant
planning (i.e., non-observable non-deterministic domains) and the 2008
competition (Bryce \& Buffet) added a track for fully-observable
non-deterministic (FOND) domains.  In the 2011 competition, we dropped
the Conformant and FOND tracks due to lack of interest, but added a
partially observed MDP (POMDP) track.  We also made a major change of
language from PPDDL to RDDL~\cite{rddl} (while providing automated
translations from RDDL to ground PPDDL and factored MDPs and POMDPs),
which allowed modeling a variety of new problems with stochasticity,
concurrency, and complex reward and transition structure not jointly
representable in lifted PPDDL.  The 2011 competition saw five MDP and
six POMDP planner entrants.

Previous competitions saw the emergence of {\sc
FF-Replan}~\cite{ffreplan} --- which replanned on unexpected outcomes
in a determinised translation of PPDDL --- as an influential and
top-performing planner.  With our language change from PPDDL to RDDL
in 2011 and our variety of new problem domains, planners based largely
on the UCT Monte Carlo tree search algorithm~\cite{uct} placed first
in both the MDP and POMDP tracks in the 2011 competition.  For the MDP
track, the winner was {\sc PROST} (Keller \& Eyerich), which used UCT
in combination with determinisation techniques to initialise
heuristics; the runner up was {\sc Glutton} (Kolobov, Dai, Mausam \&
Weld), which used an iterative deepening version of RTDP~\cite{rtdp}
with sampled Bellman backups.  For the POMDP track, the winner was
{\sc POMDPX NUS} (Wu, Lee \& Hsu), which used a Point-based Value
Iteration (PBVI) technique~\cite{sarsop} for smaller problems, but a
POMDP-variant of UCT~\cite{pomcp} for larger problems; the runner up
was {\sc KAIST AILAB} (Kim, Lee \& Kim), which used a symbolic variant
of PBVI~\cite{sim} with a number of enhancements.

Evaluation for the 2004, 2006, and 2008 competitions relied on
analysis of one or more of the following metrics: (1) average action
cost to reach the goal, (2) average number of time steps to reach the
goal, (3) percent of runs ending in a goal state, and (4) average
wall-clock planning time per problem instance.  Because lack of
planner attempts on some harder domains made it difficult to aggregate
average performance results on these metrics, we introduced an
alternate purely reward-based evaluation approach in 2011 --- for
every problem instance of every domain, a planner was assigned a
normalised $[0,1]$ score with the lower bound determined by the
maximum average performance of a noop and random policy and the upper
bound determined by the best competitor; any planner not competing or
underperforming the lower bound was assigned a score of 0 and all
normalised $[0,1]$ instance scores were averaged to arrive at a single
final score for each planner.

A recurring debate at each competition is whether problem domains have
reflected the full spectrum of probabilistic planning 
(e.g.,~\cite{probvsreplan}).  This issue partially motivated our change
from PPDDL to RDDL in 2011 in order to model stochastic domains like
multi-intersection traffic control and multi-elevator control that
could not be modeled in lifted PPDDL.  How the language and domain
choice for the 2013 IPC shapes up remains to be seen; however, given
the profound influence the uncertainty track of the IPC has had on the
direction of planning under uncertainty research in the past seven
years, we believe it is imperative that the competition domains in
2013 are chosen to ensure the greatest relevance to end applications
of interest to the planning under uncertainty community.
